package leetcode.editor.cn.dsa15_stackAndGA;
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
// 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct
//-characters 相同
//
// 示例 1： 
// 输入：s = "bcabc"
// 输出："abc"
//
// 示例 2： 
// 输入：s = "cbacdcbc"
// 输出："acdb"
//
// 提示： 
// 1 <= s.length <= 104
// s 由小写英文字母组成 
// 
// Related Topics 栈 贪心算法 字符串 
// 👍 296 👎 0

public class RemoveDuplicateLetters316 {
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateLetters316().new Solution();
        System.out.println(solution.removeDuplicateLetters("bcabc")); //abc
        System.out.println(solution.removeDuplicateLetters("cbacdcbc")); //acdb
        System.out.println(solution.removeDuplicateLetters("dcbadd")); //cbad
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            int len = s.length();
            // 结束条件：空字符串或者单字符不处理
            if (len <= 1) return s;
            // 主功能： 1. 记录每个字母最后出现位置 2.尝试找到尽可能小的首字符
            // 3.在剩余子串中删掉首字符然后递归寻找下一个首字符
            // 创建计数器，记录每个字母在字符串中最后一次出现的位置
            int[] lastOccurrence = new int[26];
            for (int i = 0; i < len; i++) {
                lastOccurrence[s.charAt(i) - 'a'] = i;
            }
            // 记录当前处理过的字符串中最小的字符位置
            int pos = 0;
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) < s.charAt(pos))
                    pos = i;
                // 发现某个字符是最后一次出现，那么满足条件的当前字符串的
                // 最小字符一定不在后面的子字符串中了，退出循环
                if (lastOccurrence[s.charAt(i) - 'a'] == i)
                    break;
            }
            // 继续处理剩下的pos之后的字符串，我们可以把pos之后字符串中
            // 重复出现的s.charAt(pos)字符去除了
            String remainedString = s.substring(pos+1)
                    .replaceAll(""+s.charAt(pos), "");
            // 关系式： f(n)=x+f(m) x为本轮找到的最小首字符， m剩余子串中剔除首字符得到的子串
            // 返回的字符串是最小首字符 + 剩下的字符串去除重复字母后的结果
            return s.charAt(pos) + removeDuplicateLetters(remainedString);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}